1. Field of the Invention
The present invention relates to systems and methods for transmitting data and in particular to a method and apparatus for switching flow paths in packet switched networks at precise times.
2. Description of the Related Art
Some data flows require reception of entire atomic data elements on a regular temporal schedule for proper utilization of the data. One example is uncompressed digital video, which has the atomic unit of a frame of video. When video flows are changed, they must be changed on the boundary of a frame, rather than during the active video within it to avoid undesirable visible artifacts. Also a video flow requires frames to be regularly delivered by the precise times of frame visual presentation. If a frame is not delivered on time, it must be dropped, also leading to undesirable visible artifacts.
When these data flows with required regularly scheduled atomic data elements are transmitted on a packet switched network, changing the path of these flows through the network can lead to two problems.
The first problem is the potential of a destination not fully receiving a required atomic data element during the flow path change. For example, one could attempt to use Internet Group Management Protocol (IGMP) to manage the delivery of multicast Internet Protocol (IP) data flows. The destination could emit an IGMP Leave Group message to leave the multicast group that receives data transmitted from one data source, and then send an IGMP Membership Report message to join the group that receives data transmitted from another data source. Depending on the behavior of the network elements and the timing of the two IGMP messages, the destination may experience an instance during the flow path change when an atomic data element does not arrive in full during the required regular period. IGMP has no guarantees of the time it takes to make requested multicast flow path changes, and the actual timing will differ by vendor, network configuration, and potentially network load.
The second problem is the potential of double bandwidth during the flow path change. In the IGMP example, the destination may begin receiving data from the new source while still receiving data from the old source, resulting in a double bandwidth requirement. Indeed, an application may seek to emit an IGMP Membership Report message to join the new group before sending an IGMP Leave Group message to leave the old group in order to ensure that there are no regular periods without receiving data. This double bandwidth requirement means that the network paths between sources and destinations needs to be capable of double the bandwidth of the flows in order to ensure that the network paths are not oversubscribed (a situation that could lead to loss of data). This can be quite a waste of network resources, as that extra bandwidth required during flow path changes is not required most of the time when the system is not changing flow paths.
Existing solutions to avoid the “double bandwidth” problem require specialized processing outside of the typical Ethernet switch hardware. If flow path changes can be made at the precise times between regular atomic elements, destination devices could be assured of uninterrupted data delivery without the network needing to be scaled for a double bandwidth requirement. However, traditional means of making such flow path changes cannot be made quickly or at precise times between regular atomic elements. Packet switched networks generally use switching devices which are designed for the high-speed switching of packets based on rules in a forwarding information base (FIB). FIB rule changes on packet switching devices are much slower than the speed that device can switch individual packets. For example, see Curtis, et al., “DevoFlow: scaling flow management for high-performance networks”, Proceedings of the ACM SIGCOMM 2011 conference, pp. 254-265 ACM New York, N.Y., USA, doi>10.1145/2018436.2018466 (describes typical FIB rule update times, “We found that the switch {ProCurve 5406zl} completes roughly 275 flow setups per second”), and Bilberry, et al., “Network Service Security Through Software-Defined Networking”, (describes FIB rule update times, “on Arista 7050S switch meeting OpenFlow 1.0 specification . . . Mean time to install a flow is 5.2 ms {192/second}, standard deviation of 3.4 ms over 250 tests. Flow updates took as little as 0.76 ms {1315/second} and as long as 15 ms {66/second}”), both of which are hereby incorporated by reference herein.
So despite the fact that data plane of some packet switches available today can switch over 1 billion packets per second, FIB rule updates run at much slower speeds, often 1000 or fewer rule updates per second. Furthermore, packet switching devices in common use today do not have a way to accurately time the instantiation of a new FIB rule. This makes it difficult to make FIB rule changes at precise times between regular atomic elements of high speed data flows.
Accordingly, there is a need for a system and method that allows flow path changes to be made at precise times between regular atomic elements without double bandwidth scaling. The present invention satisfies that need.